﻿using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using System;

namespace Util
{
    /*
     * @Author Wujiajun
     * @Date 2021/2/2-6.50pm
     * @Description 二分查找的各种模板
     * 
     */

    public class BinarySearch : MonoBehaviour
    {

        /// <summary>
        /// 模板1：用于查找可以通过访问数组中的【单个索引】来确定的元素或条件
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public int FirstBinarySearch(int[] nums, int target)
        {
            if (nums.Length == 0)
                return -1;

            int left = 0, right = nums.Length - 1;               // 两个初始索引条件
            while (left <= right)
            {
                int mid = left + (right - left) / 2;             // Prevent (left + right) overflow 避免溢出
                if (nums[mid] == target) { return mid; }
                else if (nums[mid] < target) { left = mid + 1; } // 向右查找
                else { right = mid - 1; }                        // 向左查找
            }                                                    // End Condition: left > right
            return -1;
        }
    }
}